package org.aplombh.java.interview.leetcode;

import java.util.ArrayList;
import java.util.Arrays;

public class _08_08_有重复字符串的排列组合 {
    public static void main(String[] args) {
        for (String str : new _08_08_有重复字符串的排列组合().permutation("qqe")) {
            System.out.println(str);
        }
    }

    public String[] permutation(String S) {
        char[] all = S.toCharArray();
        Arrays.sort(all);
        ArrayList<String> res = new ArrayList<>();
        boolean[] visit = new boolean[all.length];
        StringBuffer tmp = new StringBuffer();
        dfs(res, visit, tmp, all, 0);
        return res.toArray(new String[0]);
    }

    private void dfs(ArrayList<String> res, boolean[] visit, StringBuffer tmp, char[] all, int i) {
        if (tmp.length() == all.length) {
            if (!res.contains(tmp.toString())) res.add(tmp.toString());
        } else {
            for (int j = 0; j < all.length; j++) {
                if (!visit[j]) {
                    visit[j] = true;
                    tmp.append(all[j]);
                    dfs(res, visit, tmp, all, j);
                    tmp.deleteCharAt(tmp.length()-1);
                    visit[j] = false;
                }
            }
        }
    }
}